class Solution {
public:
    int trap(vector<int>& height) {
        
        int n = height.size();
        if(n<3) return 0;
        vector<int> leftmax(n, 0);
        for(int i=0; i<n; i++){
            if(i==0) leftmax[i]=height[i];
            else{
                leftmax[i] = max(leftmax[i-1], height[i]);
            }
        }
        vector<int> rightmax(n, 0);
        for(int i=n-1; i>=0; i--){
            if(i==n-1) rightmax[i]=height[i];
            else{
                rightmax[i] = max(rightmax[i+1], height[i]);
            }
        }

        int water = 0;
        for(int i=1; i<n-1; i++){
            water += min(leftmax[i], rightmax[i])-height[i];
        }

        return water;
    }
};